package com.astrob.util;

//https://www.jianshu.com/p/a31ed1e0668e?utm_campaign=maleskine&utm_content=note&utm_medium=seo_notes&utm_source=recommendation
public class Dijkstra {
    private final static int MAXVEX = 9;
    private final static int MAXWEIGHT = 100000;
    private int shortTablePath[] = new int[MAXVEX]; //记录的是V0到某订单的最短路径

    public void shortestPathDijkstra(Graph graph) {
        int min;
        int k = 0;//记录下标
        boolean isgetPath[] = new boolean[MAXVEX];

        //初始化shortTablePath
        shortTablePath = graph.getMatrix()[0];
        shortTablePath[0] = 0;
        isgetPath[0] = true;

        for (int v = 1; v < graph.getVertexSize(); v++) {
            min = MAXWEIGHT;

            //是否是到当前节点的最短路径
            for (int i = 0; i < graph.getVertexSize(); i++) {
                if (!isgetPath[i] && shortTablePath[i] < min) {
                    k = i;
                    min = shortTablePath[i];
                }
            }

            //标志k的位置当前是最短路径
            isgetPath[k] = true;

            // 判断当前节点到各个节点的当前最短路径
            for (int j = 0; j < graph.getVertexSize(); j++) {

                if (!isgetPath[j] && (min + graph.getMatrix()[k][j]) < shortTablePath[j]) {
                    shortTablePath[j] = min + graph.getMatrix()[k][j];
                }

            }

            //打印当前步骤(非必须)
            for (int i = 0; i < shortTablePath.length; i++) {
                System.out.print(shortTablePath[i] + "  ");
            }
            System.out.println();
            for (int i = 0; i < isgetPath.length; i++) {
                System.out.print(isgetPath[i] + "  ");
            }
            System.out.println();
            System.out.println();
            System.out.println();
        }

        //打印到各个节点的最短路径
        for (int i = 0; i < shortTablePath.length; i++) {
            System.out.println("V0到V" + i + "最短路径为 " + shortTablePath[i]);
        }

    }

    //打印当期那的邻接矩阵
    public void printGraph(Graph graph) {
        for (int i = 0; i < graph.getVertexSize(); i++) {
            for (int j = 0; j < graph.getMatrix()[i].length; j++) {
                if (graph.getMatrix()[i][j] < Graph.MAX_WEIGHT) {
                    System.out.print(graph.getMatrix()[i][j] + " ");
                } else {
                    System.out.print("∞" + " ");
                }
            }
            System.out.println();
        }
    }


    public static void main() {
        Graph graph = new Graph(MAXVEX);
        graph.createGraph();
        Dijkstra dijkstra = new Dijkstra();
        dijkstra.printGraph(graph);
        dijkstra.shortestPathDijkstra(graph);
    }

}

//Google Map android版和IOS版的SDK都没有集成路径规划的相关API，若要实现，只能通过http链接请求URL，携带起点终点经纬度，得到返回集合，在地图中展示。
//https://blog.csdn.net/dong_xg/article/details/54018728

//最小成本的路径
//比方说物流车要送货到 n 个地点，要寻求最便捷的路线以减少物流的时间与油费

//给定的两点之间Google地图路径规划和详情。
//https://www.cnblogs.com/wudi521/p/6052117.html

//Android OpenStreetMap（OSM） 使用 osmbonuspack 进行导航 --这个是在线的
//http://topmanopensource.iteye.com/blog/1694508
//https://blog.csdn.net/binyao02123202/article/details/20080255

//离线？
// https://blog.csdn.net/u014712516/article/details/60872310

//需要生成离线演算包
//https://github.com/graphhopper/graphhopper
